# -*- coding: utf-8 -*-            
# @Time : 2023/9/4 22:30
# @Author  : lining
# @FileName: 图的广度优先遍历.py
"""
存储方式为：邻接表
广度优先遍历，从一个点出发，到这个点最短的路径称为他的层数
https://leetcode.cn/problems/course-schedule/
示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]    0是1的先修课
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
"""
class canFinish():
    def __init__(self, numCourses):
        # 总的课程数
        self.numCourses = numCourses
        # 没有先修的课程
        self.lessons = []
        # 已经修过的课程
        self.lessons_fin = []

    # 获取每个节点能去的边，增加点的入度，入度为0则没有先修课可直接修
    def get_to_edg(self, edges):
        self.to_edg = {}
        # 点的入度
        self.in_edg = {}
        for i in edges:
            if i[0] not in self.in_edg:
                self.in_edg[i[0]] = 0
            if i[1] not in self.in_edg:
                self.in_edg[i[1]] = 0
            self.in_edg[i[0]] = self.in_edg[i[0]] + 1
            if i[1] not in self.to_edg:
                self.to_edg[i[1]] = [i[0]]
            else:
                self.to_edg[i[1]].append(i[0])
        for i in range(self.numCourses):
            # 入度为0，没有先修课，放到队列里
            if self.in_edg[i] == 0:
                self.lessons.append(i)
        # 队列不为空，则表示有课程没有先修课，就可以开始修了
        while self.lessons:
            # 先进先出
            current = self.lessons[0]
            self.lessons_fin.append(current)
            del self.lessons[0]
            # 最末尾的课不在to边
            if current in self.to_edg:
                for y in self.to_edg[current]:
                    self.in_edg[y] = self.in_edg[y] - 1
                    if self.in_edg[y] == 0:
                        self.lessons.append(y)
        if self.numCourses == len(self.lessons_fin):
            print(True)
        else:
            print(False)


edgs = [[1,0],[1,2],[2,3]]
n = 4
canFinish(n).get_to_edg(edgs)
